package com.zac.coroutine.algorithm.leetcode.array

/**
 * author zac
 * date 2024/11/6
 *给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 *
 * 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
 *
 *
 *
 * 示例 1 ：
 *
 * 输入：nums = [2,2,1]
 * 输出：1
 * 示例 2 ：
 *
 * 输入：nums = [4,1,2,1,2]
 * 输出：4
 * 示例 3 ：
 *
 * 输入：nums = [1]
 * 输出：1
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 3 * 104
 * -3 * 104 <= nums[i] <= 3 * 104
 * 除了某个元素只出现一次以外，其余每个元素均出现两次。
 */
class Test9 {
    companion object {

        @JvmStatic
        fun main(args: Array<String>) {
            singleNumber(arrayOf(4,1,2,1,2,4,6,6,5,7,7))
        }


        // 解释:
        // xor:亦或运算符 ⊕
        // 亦或运算:
        // 1.两数相同的异或运算结果为0
        // 2.一个数与0的亦或运算为其本身
        // 3.多个数的亦或运算满足交换律和结合律(重要)
        // 所以:  4,1,2,1,2,4,6,6,5,7,7 的亦或运算相当于
        // 4⊕4⊕1⊕1⊕2⊕2⊕6⊕6⊕7⊕7⊕5 相当于 0⊕5 = 5  (即使在循环中也满足,不知道为什么)

        //*给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
        fun singleNumber(nums: Array<Int>): Int {
            var result = 0
            for (num in nums) {
                result = result xor num
            }

            return result
        }
    }
}